//33. 搜索旋转排序数组
//思路：搜索的时间复杂度限制在O(logN)，意味着是二分查找
//这里的数组是旋转后的，我们二分查找的时候将一个数组分为两段来查找，左右两端分别是有序的
//如果target不在左半边的数组里，那么就在右半边的数组中查找

int search(int* nums, int numsSize, int target){
    int left = 0, right = numsSize-1;
    while(left <= right)
    {
        int mid = left + (right-left)/2;
        if(nums[mid] == target) return mid;
        if (nums[left] <= nums[mid])
        {
            if(nums[left] <= target && target < nums[mid])
                right = mid - 1;
            else
                left = mid + 1;
        }
        else
        {
            if(nums[mid] < target && target <= nums[right])
                left = mid + 1;
            else
                right = mid - 1;
        }
    }
    return -1;
}